#ifndef _math_tetration_h_
#define _math_tetration_h_

#include<math/gcd.h>
#include<math/pow.h>
#include<math/phi.h>

namespace contest
{
/**
 * Calculates the tetration.
 * @param base: The number to be raised.
 * @param exp: The exponent.
 * @param mod: The modulo of the exponent.
 **/
uint32_t tetration(const uint32_t base, const uint32_t size, const uint32_t mod)
{
    if (size == 1)
    {
        return base % mod;
    }
    if (mod == 1)
    {
        return 0L;
    }
    uint32_t d = gcd(base, mod);
    uint32_t exp;
    if (d == 1)
    {
        exp = tetration(base, size - 1, phi(mod));
        return pow(base, exp, mod);
    }
    else
    {
        /*
        uint32_t totient = phi(mod/d);
        exp = tetration(base, size - 1, totient);
        uint64_t l = pow(base/d, exp, mod/d);

        uint64_t r = pow(     d, exp, mod/d) * pow(d, totient-1, mod/d);
        return (l * r * d) % mod;
        */
        return -1;
    }
}
}

#endif
